#include <iostream>

using namespace std;

//节点 FIXME: `Node` is better, 类型名字首字母大写
template <class T>
struct node {
public:
    T element;
    node<T> *next;
    node<T> *before;
    node(){
        this->element=0;
        this->next=NULL;
        this->before=NULL;
    }
    node(T &element){
        this->element=element;
        this->next=NULL;
        this->before=NULL;
    }
};

template <class T>
class chain: public node<T>
{
public:
    node<T> *header;
    int listsize;
    node<T> *cur;

public:
    chain()
    {
        header=NULL;
        cur=NULL;
        listsize=0;
    }
    
    void add(int theElement)
    {
        node<T> *point= new node<T>(theElement);
        point->element=theElement;
        if(header==NULL){
            header=point;
            header->element=theElement;
            header->before=header;
            header->next=header;
        }
        else{
            // FIXME: `cur`的含义是什么？能否直接找到最优的位置再插入？
            node<T> *temp=cur->next;
            cur->next=point;
            point->next=temp;
            point->before=cur;
            temp->before = point;
        }
        cur=point;
        
        //根据其双向还有序的特点,可以插入排序
        listsize++;
        node<T> *p1= cur->before;
        int counter=0;
        int t=0;
        while(p1!=header){
            if(cur->element<p1->element){
                counter+=1;
                t=p1->element;
                p1=p1->before;
            }
            else{break;}
        }
        p1->next->element=theElement;
        p1=p1->next;
        
        if(counter>0) {
            for(int i=0;i<counter-1;i++){
                cur->element=cur->before->element;
                cur=cur->before;
            }
            cur->element=t;
        }
    }
};

int main()
{
    chain<int> n1;
    int str;
    int i=0;
    while (cin >> str) {
        n1.add(str);
        i++;
        if(i>=4){break;}
     }
    node<int> *p2=n1.header;
    for(int j=0;j<n1.listsize;j++){
        cout<<p2->element<<endl;
        p2=p2->next;
    }
    return 0;
}

/*最后还留点小bug，当新插入的值比头节点还小的时候老是出错，看自己的代码感觉逻辑上说的过去...后面再研究研究
第四题的难度比起前面大很多，但仅对链表而言这几个题感觉还是不够的，看教材上可以利用链表完成箱子排序、基数排序、凸包等问题，挺有趣的并且
就逻辑而言还是能看懂的，但是一用代码实现就眼高手低，还是需要多加练习*/

// FIXME: 
//  1. 做的挺好的，继续努力！
//  2. 可以把这个问题放一下，过一段时间再看，也许能找到问题。
//  3. 其他的程序，参考我给你的建议改进一下。
